package zuo.middleLevel_3;

import zuo.baseUP1_Hash.Hash;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;

/**
 * @Author: Forx
 * @Data: 2021/6/22
 * @Desc: Algorithm - zuo.middleLevel_3
 * @Version: v1.0
 */
public class ML3 {
/**
 *
 * 有n个打包机器从左到右一字排开，上方有一个自动装置会抓取一批放物品到每个打
 * 包机上，放到每个机器上的这些物品数量有多有少，由于物品数量不相同，需要工人
 * 将每个机器上的物品进行移动从而到达物品数量相等才能打包。每个物品重量太大、
 * 每次只能搬一个物品进行移动，为了省力，只在相邻的机器上移动。请计算在搬动最
 * 小轮数的前提下，使每个机器上的物品数量相等。如果不能使每个机器上的物品相同，
 * 返回-1。
 * 例如[1,0,5]表示有3个机器，每个机器上分别有1、0、5个物品，经过这些轮后：
 * 第一轮：10<-5=>114第二轮：1<-1<-4=>213第三轮：
 * 21<-3=>222
 * 移动了3轮，每个机器上的物品相等，所以返回3
 * 例如[2,2,3]表示有3个机器，每个机器上分别有2、2、3个物品，
 * 这些物品不管怎么移动，都不能使三个机器上物品数量相等，返回-1
 *
 * 看每一个数,左边需要多少个,右边需要多少个
 *  如果左右两边都需要,那么此时的至少的移动次数
 *  是|left|+|right|
 *  如果左边大于平均值,右边小于平均值那就是max(|left|,|right|)
 *  如果两边都大于平均值,则至少移动的次数是max(|left|,|right|)
 *
 * */
    public static int getMinMove(int[] arr){
        //平均值肯定是整数
        long sum = 0;
        long[] sumArr = new long[arr.length];
        for (int i = 0; i < arr.length; i++) {
            sumArr[i] = sum;
            sum+=arr[i];
        }
        if((sum%(arr.length-1))!=0)return -1;
        PriorityQueue<Integer> ans = new PriorityQueue<Integer>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        int avg =(int) sum/(arr.length);
        ans.add((int)Math.abs(avg*(arr.length-1) - sum+arr[0]));
        ans.add((int)Math.abs(avg*(arr.length-1) - sumArr[arr.length-1]));
        for (int i = 1; i < arr.length-1; i++) {
            int leftGet =(int) (avg*i - sumArr[i]);
            int rightGet = (int)(avg*(arr.length-i-1) - (sum-sumArr[i] - arr[i]));
            if(leftGet > 0 && rightGet >0 ){
                ans.add(leftGet+rightGet);
            }else {
                ans.add(Math.max(Math.abs(leftGet),Math.abs(rightGet)));
            }
        }
        return ans.poll();
    }
    public static int getMinMoveOPT(int[] arr){
        int size = arr.length;
        int sum = 0;
        for (int i = 0; i < size; i++) {
            sum+=arr[i];
        }
        if(sum%size!=0)return -1;
        int avg = size/size;
        int leftSum = 0;
        int ans = 0;
        for (int i = 0; i < size; i++) {
            int leftRest = leftSum-i*avg;
            int rightRest = (sum - leftSum -arr[i]) - avg*(size-i-1);
            if(leftRest<0 && rightRest <0){
                ans = Math.max(ans,Math.abs(leftRest)+Math.abs(rightRest));
            }else {
                ans = Math.max(ans,Math.max(Math.abs(leftRest),Math.abs(rightRest)));
            }
            leftSum+=arr[i];
        }
        return ans;
    }
    /**
     * 顺时针方向打印矩阵
     * direction:
     *         0 : left-right
     *         1 : right-down
     *         2 : right-left
     *         3 : up-left
     * */
    public static void printMatrix(int[][] arr,int startX,int startY,int endX,int endY,int direction){
        if(startX <0 || startX>arr.length-1 ||
                startY <0 || startY>arr.length-1 ||
                endX <0 || endX>arr.length-1 ||
                endY <0 || endY>arr.length-1)return;
        if(!(endX>=startX && endY>=endX))return;
        if(direction==0){
            for (int i = startX; i <= endX; i++) {
                System.out.print(arr[startY][i]);
                System.out.print(" ");
            }
            printMatrix(arr,startX,startY+1,endX,endY,(direction+1)%4);

        }else if(direction==1){
            for (int i = startY; i <=endY ; i++) {
                System.out.print(arr[i][endX]);
                System.out.print(" ");
            }
            printMatrix(arr,startX,startY,endX-1,endY,(direction+1)%4);

        }else if(direction==2){
            for (int i = endX; i >=startX ; i--) {
                System.out.print(arr[endY][i]);
                System.out.print(" ");
            }
            printMatrix(arr,startX,startY,endX,endY-1,(direction+1)%4);

        }else if(direction==3){
            for (int i = endY; i >=startY ; i--) {
                System.out.print(arr[i][startX]);
                System.out.print(" ");
            }
            printMatrix(arr,startX+1,startY,endX,endY,(direction+1)%4);
        }
    }

    /**
     * 旋转正方形矩阵
     *
     * 要求空间复杂度O(1)
     * */
    public static void rotated(int[][] arr){
        int limit = arr.length/2;

        int len = arr.length;

        for (int i = 0; i < limit; i++) {
            int groups = arr.length-1-2*i;
            for (int j = 0; j < groups; j++) {
                int temp = arr[i][i+j];
                arr[i][i+j] = arr[len-1-i-j][i];
                arr[len-1-i-j][i] = arr[len-1-i][len-1-i-j];
                arr[len-1-i][len-1-i-j] = arr[i+j][len-1-i];
                arr[i+j][len-1-i] = temp;
            }
        }
    }
    /**
     * 斜着走Z字形打印二维数组
     * */
    public static void printMatrixZ(int[][] arr){
        int flag = 0;
        int cols = arr[0].length;
        int rows = arr.length;
        int index = 0;
        for (int i = 0; i < cols; i++) {
            printMatrixClineV2(arr,0,i,((flag++)%2));
        }
        for (int i = 1; i < rows; i++) {
            printMatrixClineV2(arr,i,cols-1,(flag++%2));
        }

        //System.out.println(arr[rows-1][cols-1]);
    }
    //flag = 0 t-d 1:d-t
    public static void printMatrixCline(int[][] arr,int x,int y,int flag){
        int index = 0;
        if (flag == 0) {//t-d
            for (int i = y; isContainElm(arr,x,y);) {
                System.out.print(arr[x++][y--]);
                System.out.print(" ");
            }
        }else {
            for (int i = x; isContainElm(arr,x,y);) {
                System.out.print(arr[x--][y++]);
                System.out.print(" ");
            }
        }
    }
    public static void printMatrixClineV2(int[][] arr,int x,int y,int flag){
        int reflexX = 0;
        int reflexY = 0;
        if(arr.length == arr[0].length){
            reflexX = y;
            reflexY = x;
        }else if(arr.length > arr[0].length){
            reflexX = Math.min(x+y,arr.length-1);
            reflexY = x+y-reflexX;
        }else {
            reflexX = Math.min(arr.length-1,y);
            reflexY = x+y-reflexX;
        }
        if(flag==1){
            printMatrixCline(arr,reflexX,reflexY,1);
        }else {
            printMatrixCline(arr,x,y,0);
        }
    }

    public static boolean isContainElm(int[][] arr,int row,int col){
        if(row<0 || col <0 || row>=arr.length || col >=arr[0].length){
            return false;
        }
        return true;
    }
    /**
     * 假设s和m初始化，s="a";m=s;
     * 再定义两种操作，第一种操作：
     * m=s;
     * s=s+s;
     * 第二种操作：
     * s=s+m;
     * 求最小的操作步骤数，可以将s拼接到长度等于n
     * */
    /**
     * 这个方法不对 操作1中的两个操作不能分离
     * 正确的方法是
     * 如果n是质数,则最少的次数就是调用op2的次数
     * 如果不是质数,那就向下分成质数
     * */
    public static int getMinKinds(int n){
        if(n==0)return 0;
        if(n==1)return 1;
        return getMinKinds((int) (n-Math.pow(2,(int)(Math.log(n)/Math.log(2)))))+1;
    }
    /**
     *  给定一个字符串类型的数组arr,求出现次数最多的前K个
     *  hashMap and heap
     *
     *
     * */
    /**
     * 实现一个结构,
     * 有两个方法
     * 1.接受用户字符串
     * 2.printTopK
     * */
    public static class TopK{
        private static class Node{
            public String str;
            public int times;

            public Node(String str, int times) {
                this.str = str;
                this.times = times;
            }

            public Node() {
            }
        }
        private   HashMap<String,Node> strFreqTable;
        private  HashMap<Node,Integer> strIndexTable;
        private Node[] heap;
        private  int sizeK;

        public TopK(int sizeK) {
            this.sizeK = 0;
            heap = new Node[sizeK];
        }
        public void add(String string){
            Node cur = null;
            int curIndex = -1;
            if(!strFreqTable.containsKey(string)){
                cur = new Node(string,1);
                strFreqTable.put(string,cur);
                strIndexTable.put(cur,-1);
            }else {
                cur = strFreqTable.get(string);
                cur.times++;
                curIndex = strIndexTable.get(cur);
            }
            if(curIndex==-1){//
                if(sizeK == heap.length){
                    if(heap[0].times < cur.times){
                        strIndexTable.put(heap[0],-1);
                        strIndexTable.put(cur,0);
                        heap[0] = cur;
                        heapify(0,sizeK);
                    }

                }else {
                    strIndexTable.put(cur,sizeK);
                    heap[sizeK] = cur;
                    insertHeap(sizeK++);
                }
            }else {
                heapify(curIndex,sizeK);
            }

        }
        public  String[] getTopK(){
            String[] ans = new String[heap.length];
            for (int i = 0; i < heap.length; i++) {
                ans[i] = heap[i].str;
            }

            return ans;
        }
        private void swap(int index1,int index2){
            strIndexTable.put(heap[index1],index2);
            strIndexTable.put(heap[index2],index1);
            Node temp = heap[index1];
            heap[index1] = heap[index2];
            heap[index2] = temp;
        }
        private void insertHeap(int index){
            while (index!=0){
                int parent = (index-1)/2;
                if(heap[index].times < heap[parent].times){
                    swap(index,parent);
                    index = parent;
                }else {
                    break;
                }
            }
        }
        private void heapify(int index,int size){
            int l = index*2+1;
            int r = l+1;
            int smallest = index;
            while (l < size){
                if(heap[l].times < heap[index].times){
                    smallest = l;
                }
                if(r < size && heap[r].times < heap[smallest].times) {
                    smallest = r;
                }
                if(smallest != index){
                    swap(smallest,index);
                }

                index = smallest;
                l = index*2+1;
                r = l+1;
            }
        }



    }





    public static void main(String[] args) {
        int[][] matrix = {
//                {1,2,3,4},
//                {5,6,7,8},
//                {9,10,11,12},
//                {13,14,15,16},
                {1,2},
                {3,4},
                {5,6},
        };
        System.out.println(getMinKinds(100));
//        printMatrixZ(matrix);
//        for (int i = 1; i < 100; i++) {
//            System.out.println(Math.pow(2,(int)(Math.log(i)/Math.log(2))));
//        }
        //
        //printMatrix(matrix,0,0,3,3,0);
        //printMatrixCline(matrix,2,2,0);
//        rotated(matrix);
//        for (int i = 0; i < matrix.length; i++) {
//            System.out.println(Arrays.toString(matrix[i]));
//        }
    }

}
